求值
题目 求值
思路分析
问题是有100个约数的最小的数是多少 因为是填空题 所有最暴力的想法就是 直接从小到大枚举 看每个数有多少个约数 第一次找到约数数量有100个的数时 就是答案
约数数量怎么求呢
可以用试除法 把一个数的所有约数找出来放在set里 最后返回set的size 就是该数的约数数量
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const int N=100010;
int counts(int n){
set<int> res;
for(int i=1;i<=n/i;i++){
if(n%i==0){
res.insert(i);
res.insert(n/i);
}
}
return res.size();
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i=0;i<1000000;i++){
if(counts(i)==100){
cout<<i;
return 0;
}
}
return 0;
}
相当暴力 但也是得到了正确答案
填空题 这题其实可以这样过了
但是 复习一下约数
约数个数有个公式
把一个数N 写成：N = (p1^x1)(p^x2)(p3^x3)…(pk^xk)，其中pi为质数。
则N的约数个数为：(x1+1)(x2+1)(x3+1)…(xk+1)
但是貌似并不适用 因为这个公式适用于知道因子的情况 而这里并不知道因子 还得把因子求出来 再套公式 那既然求出了因子 直接放set里其实更快
如果对于一个给定数 n 需要计算它的约数个数，存在两种基本方法：
1. 试除法（暴力方法）
您提到的使用试除法是直接且直观的方法，这种方法的优点是编码简单，适合于范围较小或约数数量较少的数。具体实现方式如您所示，通过遍历从 1 到 \(\\sqrt{n}\) 的所有整数来检查每个数是否为 n 的约数，如果是，则它和 n 除以它的结果都是约数。
2. 分解质因数法
此方法基于数的质因数分解，如您所述，一个数 N 可以表示为 \(N=p_1^{x_1}\cdot p_2^{x_2}\cdots p_k^{x_k}\)，其中 \(p_i\) 是质数，\(x_i\) 是对应的指数。然后，N 的约数个数是
使用这种方法需要先找出 n 的所有质因数及其指数。这可以通过试除法进行，即从最小的质数开始，尝试能否整除 n，并计算每个质数的指数。然后应用上述公式计算约数总数。这种方法的复杂度取决于 n 的质因数分解速度，对于大数而言，如果其因数结构复杂（如有很多小的质因数），则这种方法会比直接计算约数要快。
对于问题的应用
如果问题是找到最小的数，它恰好有 100 个约数，暴力方法虽然直接但效率较低，特别是当数变得很大时。质因数分解方法在找到最小的满足条件的数时可能更高效，因为它允许我们快速计算一个数的约数个数，而不必实际地找出所有约数。
示例代码优化
考虑到约数个数的计算，如果使用质因数分解方法，代码可以修改为：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
int divisorCount(int n) {
int cnt = 1;
for (int i = 2; i <= n / i; ++i) {
if (n % i == 0) {
int power = 0;
while (n % i == 0) {
n /= i;
++power;
}
cnt *= (power + 1);
}
}
if (n > 1) cnt *= 2;
return cnt;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
for (int i = 1; ; ++i) {
if (divisorCount(i) == 100) {
cout << i << endl;
break;
}
}
return 0;
}
这种优化考虑了除法和质因数分解，更适合处理较大的数字和复杂的约数问题。
代码2真的会比代码1效率高吗 在我看来也是找到了一个属的所有约数吧 它甚至对每个约数做了额外的操作 如果更优 体现在哪里
对于比较两段代码的效率，我们首先要了解它们的计算原理和复杂度。两者都是计算一个数字的约数数量，但方法和内部操作有所不同。
试除法与质因数分解法的比较：
试除法 (第一段代码)
- 操作：对于每个整数 i，检查 n % i == 0。如果为真，则 i 和 n/i 都是 n 的约数。
- 复杂度：对于每个数，最坏情况下的操作次数是 \(O(n)\)，因为它检查从 1 到 \(n\) 的所有整数。
- 数据结构：使用 set 存储约数，保证唯一性，但插入操作平均具有 \(O(\log k)\) 的时间复杂度，其中 k 是集合中元素的数量。
质因数分解法 (第二段代码)
- 操作：对于每个整数 i，同时计算 n 由 i 整除的次数（即 i 的幂），直到 n 不再被 i 整除。
- 复杂度：对每个质因子 i 执行整除操作，最坏情况下是 \(O(n)\)。但由于它跳过了所有已经被较小的质因子整除的数，这通常比简单的试除法要快。
- 数据结构：没有使用额外的数据结构来存储约数，而是直接通过乘法计算总约数数目，省去了存储和查找的时间。
效率对比
- 数据存储：第一段代码使用 set，这意味着每找到一个新约数都需要进行插入操作。尽管 set 操作是对数时间复杂度，但是在频繁插入时仍然会造成时间消耗。而第二段代码直接通过计算获得结果，没有额外的数据存储和管理开销。
- 计算次数：第二段代码在确定 i 是 n 的质因数后，会立即计算 i 的幂，这避免了对每个 i 的多次重复检查。而第一段代码对每个 i 只做一次检查，但需要额外处理 n/i。
- 内部循环：第二段代码减少了循环中的重复计算。当 i 不再是 n 的因数时，它跳出内层循环，而第一段代码则对每个 i 至少计算两次（i 和 n/i）。
总结
虽然两者在理论上都是 \(O(n)\) 的时间复杂度，质因数分解法在实际应用中往往效率更高，特别是对于大数。它避免了不必要的存储和管理开销，并且减少了重复计算。因此，在处理需要频繁计算大量数的约数数量的情况下，质因数分解法通常是更优的选择。
代码实现
💬 评论